package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

/*
假设我们有8种不同面值的硬币{1, 2, 5, 10, 20, 50, 100, 200}
用这些硬币组合构成一个给定的数值n

例如n=200，那么其中1种可能的组合方式
200 = 3*1 + 1*2 + 1*5 + 2*20+1*50+ 1*100
问总共有多少种可能的组合方式? (这道题目来自著名编程网站ProjectEuler)

类似的题目还有：
[华为面试题] 1分2分5分的硬币三种，组合成1角，共有多少种组合

[创新工厂笔试题] 有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n


 */
public class c硬币表示 {
	public static void main(String[] args) {
		int res1 = forceHuaWei(10);
		System.out.println("华为题：" + res1);
		int res2 = useRecursionChuangXinGongChang(10);
		System.out.println("创新工厂题：" + res2);
		int res3 = recursionProjectEuler(10);
		System.out.println("ProjectEuler题：" + res3);
	}
	
	/**
	 * 迭代形式
	 * @param n
	 * @return
	 */
	public static int recursionProjectEuler(int n) {
		int[] coins = new int[] {1, 2, 5, 10, 20, 50, 100, 200};
		int[][] dp = new int[coins.length][n + 1];//有coins.length行，n+1列
		for (int i = 0; i < coins.length; i++) {//第0列全部只有1种“组合可能”；因为第0列代表“面值=0”
			dp[i][0] = 1;
		}
		for (int j = 0; j < n + 1; j++) {//第1行全部只有1种“组合可能”；因为第1行代表“纸币1对任意面值给出的组合可能”
			dp[0][j] = 1;
		}
		for (int i = 1; i < coins.length; i++) {//从第2行(纸币2)，
			for (int j = 1; j < n + 1; j++) {//第2列(面值=1)开始
				for (int k = 0; k <= j / coins[i]; k++) {
					dp[i][j] += dp[i - 1][j - k * coins[i]];//这行很巧妙地运用了“j - k * coins[i]”；
					//j / coins[i] 的值其实就是当前面值j能承受多少当前的纸币coins[i]；
					//j - k * coins[i] 通过控制k的数量，实现“有多少个当前纸币coins[i]的情况”
					//看不懂可以去看蓝桥杯7.4 的视频 32：18处
				}
			}
		}
		return dp[coins.length - 1][n];
	}
	
	/**
拿10举例：
		-0*10	-0*5	-0*2	-10*1
						-1*2	-8*1
						-2*2	-6*1
						-3*2	-4*1
						-4*2	-8*1
						-5*2	-0*1
				-1*5	-0*2	-5*1
						-1*2	-3*1
						-2*2	-1*1
				-2*5	-0*2	-0*1
		-1*10	-0*5	-0*2	-0-1
	 * @param n
	 * @return
	 */
	public static int useRecursionChuangXinGongChang(int n) {
		if (n <= 0) {
			System.out.println("特殊情况");
			return 0;
		}
		int[] coins = new int[] {1, 2, 5, 10};
		return recursionChuangXinGongChang(n, coins, coins.length - 1);
	}
	
	/**
	 * 递归形式
	 * @param n
	 * @return
	 */
	public static int recursionChuangXinGongChang(int n,int[] coins, int current) {
		if (current == 0) {//递归出口
			return 1;//当指针指向coins[0]，只有一种方法拼凑，即用1分的拼凑
		}
		int res = 0;
		for (int i = 0; i * coins[current] <= n; i++) {//从最大的零钱开始尝试；最大零钱的数量从0开始
			int remainder = n - i * coins[current];
			res += recursionChuangXinGongChang(remainder, coins, current - 1);//循环中使用递归；
		}
		return res;
	}
	
	/**
	 * 暴力形式
	 * O(N^3)
	 * @param n
	 * @return
	 */
	public static int forceHuaWei(int n) {
		int number = 0;
		int Tenchu1 = 10;// 10/1
		int Tenchu2 = 5;// 10/2
		int Tenchu5 = 2;// 10/5
		for (int i = 0; i < Tenchu1 + 1; i++) {
			for (int j = 0; j < Tenchu2 + 1; j++) {
				for (int k = 0; k < Tenchu5 + 1; k++) {
					if (i * 1 + j * 2 + k * 5 == n) {
						number++;
						System.out.println("i = " + i + " j = " + j + " k = " + k);
					}
				}
			}
		}
		return number;
	}
}
